package ch2.part4;

/**
 * 散列表的简单实现，最优实现为JDK8中的HashMap
 * <a href="https://lwx19960428.gitee.io/2019/04/28/HashMap%E6%BA%90%E7%A0%81%E9%98%85%E8%AF%BB%E7%AC%94%E8%AE%B0/">建议参考源码实现</a>
 * 采用数组加链表的方式进行实现
 * 实现了put(),get(),remove()三个方法
 * 时间复杂度：O(n)≈1
 *
 * @author liuwanxiang
 * @version 2019/05/14
 */
public class MyDict<K, V> {

    private Node<K, V>[] table;
    private int size;
    private final float loadFactor;

    public MyDict() {
        this.loadFactor = 0.75f;
    }

    /**
     * 置入元素
     *
     * @param k
     * @param v
     * @return
     */
    public V put(K k, V v) {
        return putVal(hash(k), k, v);
    }

    /**
     * 查询元素
     *
     * @param k
     * @return
     */
    public V get(K k) {
        Node<K, V> node;
        return (node = getNode(hash(k), k)) == null ? null : node.value;
    }

    /**
     * 删除元素
     *
     * @param k
     * @return
     */
    public V remove(K k) {
        Node<K, V> node;
        return (node = removeNode(hash(k), k, null, false)) == null ? null : node.value;
    }

    /**
     * 删除节点
     *
     * @param hash
     * @param key
     * @param value
     * @param matchValue
     * @return
     */
    private Node<K, V> removeNode(int hash, K key, V value, boolean matchValue) {
        Node<K, V>[] tab;
        Node<K, V> p;
        int n, index;
        if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) {
            Node<K, V> node = null, e;
            K k;
            V v;
            // 查找元素
            if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) {
                node = p;
            }


            // 开始删除元素
            if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) {
                if (node == p) {
                    tab[index] = node.next;
                } else {
                    p.next = node.next;
                }
                --size;
                return node;
            }

        }
        return null;
    }

    /**
     * 查询节点
     *
     * @param hash
     * @param key
     * @return
     */
    private Node<K, V> getNode(int hash, K key) {
        Node<K, V>[] tab;
        int n;
        Node<K, V> first, e;
        K k;
        if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
            if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k)))) {
                return first;
            }
            if ((e = first.next) != null) {
                do {
                    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
                        return e;
                    }
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

    /**
     * 置值
     *
     * @param hash
     * @param key
     * @param value
     * @return
     */
    private V putVal(int hash, K key, V value) {
        Node<K, V>[] tab = table;
        int n, i;
        Node<K, V> p;
        if (tab == null || (n = tab.length) == 0) {
            n = (tab = resize()).length;
        }
        if ((p = tab[i = (n - 1) & hash]) == null) {
            tab[i] = new Node<K, V>(hash, key, value);
        } else {
            Node<K, V> e;
            K k;
            if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) {
                // 链表的头结点key与当前key一致
                e = p;
            } else {
                for (int binCount = 0; ; binCount++) {
                    // 遍历链表
                    if ((e = p.next) == null) {
                        // 空节点
                        p.next = new Node<K, V>(hash, key, value);
                        break;
                    }
                    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
                        // 某节点key与当前key一致
                        break;
                    }
                    p = e;
                }
            }
            // 相当于原值替换，不会涉及到size增加
            if (e != null) {
                V oldVal = e.value;
                e.value = value;
                return oldVal;
            }

        }
        if (++size > table.length * loadFactor) {
            resize();
        }
        return null;
    }

    /**
     * 主数组扩容
     *
     * @return
     */
    private Node<K, V>[] resize() {
        Node<K, V>[] oldTab = table;
        Node<K, V>[] newTab = null;
        // 构建新的数组
        if (oldTab == null || oldTab.length == 0) {
            newTab = (Node<K, V>[]) new Node[16];
        } else {
            int newTabLength = table.length << 1;
            newTab = (Node<K, V>[]) new Node[newTabLength];
        }
        table = newTab;
        // 老数组中的元素重分配
        if (oldTab != null) {
            for (int i = 0; i < oldTab.length; i++) {
                Node<K, V> e;
                if ((e = oldTab[i]) != null) {
                    oldTab[i] = null;
                    if (e.next == null) {
                        newTab[e.hash & (newTab.length - 1)] = e;
                    } else {
                        Node<K, V> loHead = null, loTail = null;
                        Node<K, V> hiHead = null, hiTail = null;
                        Node<K, V> next;

                        do {
                            next = e.next;
                            if ((e.hash & oldTab.length) == 0) {
                                if (loHead == null) {
                                    loHead = e;
                                } else {
                                    loTail.next = e;
                                }
                                loTail = e;
                            } else {
                                if (hiHead == null) {
                                    hiHead = e;
                                } else {
                                    hiTail.next = e;
                                }
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[i] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[i + oldTab.length] = hiHead;
                        }
                    }

                }
            }
        }
        return newTab;
    }

    /**
     * 求对象hash的方法
     *
     * @param t
     * @return
     */
    private int hash(K t) {
        int hash;
        return (t == null) ? 0 : (hash = t.hashCode()) ^ (hash >>> 16);
    }

    /**
     * 节点Node的内部类实现
     *
     * @param <K>
     * @param <V>
     */
    private static final class Node<K, V> {
        private K key;
        private V value;
        private int hash;
        private Node<K, V> next;

        private Node(int hash, K k, V v) {
            this.hash = hash;
            this.key = k;
            this.value = v;
        }
    }

    public static void main(String[] args) {

        MyDict<String, Integer> dict = new MyDict<String, Integer>();
        dict.put("hello", 1);
        dict.put("world", 2);
        System.out.println(dict.put("world", 3));

        dict.put("world1", 3);
        dict.put("world2", 3);
        dict.put("world3", 3);
        dict.put("world4", 3);
        dict.put("world5", 3);
        dict.put("world6", 3);
        dict.put("world7", 3);
        dict.put("world8", 3);
        dict.put("world9", 3);
        dict.put("world10", 3);
        dict.put("world11", 3);

        System.out.println(dict);

        System.out.println(dict.get("hello"));
        System.out.println(dict.get("hello1"));

        System.out.println(dict.remove("world"));
        System.out.println("=========");

    }

}
